// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-05 19:21
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

@SuppressWarnings("ALL")
public class SortedArrayToBST {
    /**
     * 根据升序数组构建平衡二叉树
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        // 递归构造 -> 假设数组的值只有三个 -> 中间的作为根节点，左右两个分别作为叶子节点
        int n = nums.length;
        if (n == 0) {
            return null;
        }
        int mid = n / 2;
        // 根节点确定
        TreeNode root = new TreeNode(nums[mid]);
        // 构建左子树
        root.left = constructTree(nums, 0, mid - 1);
        // 构建右子树
        root.right = constructTree(nums, mid + 1, n - 1);
        return root;
    }

    /**
     * 根据升序数组构建平衡二叉树
     *
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private TreeNode constructTree(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        if (start == end) {
            return new TreeNode<Integer>(nums[start]);
        }
        int mid = (start + end) >> 1;
        int n = end - start;
        TreeNode root = new TreeNode(nums[mid]);
        // 构建左子树
        root.left = constructTree(nums, start, mid - 1);
        // 构建右子树
        root.right = constructTree(nums, mid + 1, end);
        return root;
    }

}


